// #include <stdio.h>
// #include <stdbool.h>
// #include <limits.h>
// #include <stdlib.h>
// #include"windows.h"
//
// // 二叉树节点结构体
// typedef struct TreeNode {
//     int val;
//     struct TreeNode* left;
//     struct TreeNode* right;
// } TreeNode;
//
// typedef struct StackNode {
//     TreeNode *node;
//     struct StackNode *next;
// } StackNode;
//
// typedef struct Stack {
//     StackNode *top;
// } Stack;
//
// // 初始化栈
// void initStack(Stack *s) {
//     s->top = NULL;
// }
//
// // 创建新节点
// TreeNode* createNode(int val) {
//     TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
//     node->val = val;
//     node->left = NULL;
//     node->right = NULL;
//     return node;
// }
//
// int pre=-1234567;
//
// // 递归方法
// int isValidBSTHelper(TreeNode* root) {
//     int a,b;
//    if(root==NULL) {
//        return 1;
//    }else {
//        a=isValidBSTHelper(root->left);
//        if(a==0||root->val<pre) {
//            return 0;
//        }
//        pre=root->val;
//        b=isValidBSTHelper(root->right);
//        return b;
//    }
// }
//
// void push(Stack* s,TreeNode* node) {
//     StackNode* newNode=(StackNode*)malloc(sizeof(StackNode));
//     newNode->node=node;
//     newNode->next=s->top;
//     s->top=newNode;
// }
//
// TreeNode* pop(Stack* s) {
//     if(s==NULL) {
//         return NULL;
//     }
//     StackNode* temp=s->top;
//     TreeNode* node=temp->node;
//     s->top=s->top->next;
//     free(temp);
//     return node;
// }
//
// // 非递归方法
// int isValidBSTNonRecursive(TreeNode* root) {
//     if(root==NULL) {
//         return 1;
//     }
//     Stack s;
//     initStack(&s);
//     TreeNode* node=root;
//     TreeNode* pre=NULL;
//     while (node!=NULL||s.top!=NULL) {
//         while (node!=NULL) {
//             push(&s,node);
//             node=node->left;
//         }
//         node=pop(&s);
//         if(pre!=NULL&&node->val<=pre->val) {
//             return 0;
//         }
//         pre=node;
//         node=node->right;
//     }
//     return 1;
// }
//
// int main() {
//     SetConsoleOutputCP(CP_UTF8);
//     // 构建测试二叉树
//     TreeNode* root = createNode(5);
//     root->left = createNode(3);
//     root->right = createNode(7);
//     root->left->left = createNode(2);
//     root->left->right = createNode(4);
//     root->right->left = createNode(6);
//     root->right->right = createNode(8);
//     if(isValidBSTHelper(root)) {
//         printf("递归方法:是二叉排序树\n");
//     }else {
//         printf("递归方法:不是二叉排序树\n");
//     }
//     // 测试非递归方法
//     if (isValidBSTNonRecursive(root)) {
//         printf("非递归方法：是二叉排序树\n");
//     } else {
//         printf("非递归方法：不是二叉排序树\n");
//     }
//
//
//     return 0;
// }